package com.yuufa.test.ex;

import com.yuufa.util.Tool;

public class Ex5 {

    public static void main(String[] args) {

        int n = 5;
        int[] s = Tool.randomHeap(5);

        Heap.sort(s, n);

        Tool.output(s, 1, n);
    }
}

class Heap { // MaxHeap
    
    public static void sort(int[] s, int n) {
        
        // max heap
        for(int i=n/2;i>=1;i--) {
            adjust(s, i, n);
        }
        
        int t = s[1]; s[1] = s[n]; s[n] = t;
        
        for(int i=n-1;i>=1;i--) {
            adjust(s, 1, i);
            t = s[1]; s[1] = s[i]; s[i] = t;
        }
    }
    
    public static void adjust(int[] s, int index, int n) {
        
        int j = 2 * index;
        int t = s[index];
        boolean finish = false;
        
        while(j<=n && !finish) {
            if(j<n) {
                if(s[j] < s[j+1]) {
                    j++;
                }
            }
          
            if(t < s[j]) {
                s[j/2] = s[j];
                j=j*2;
            } else {
                finish = true;
            }
        }
        
        s[j/2] = t;
    }
}

class Quick {
    
    public static void sort(int[] s, int left, int right, int n) {
        
        if(left <= right) {
            int k = partition(s, left, right, n);
            sort(s, left, k-1, n);
            sort(s, k+1, right, n);
        }
    }
    
    public static int partition(int[] s, int left, int right, int n) {
        int pivot = s[left];
        int i = left; 
        int j = right + 1;
        
        while(i<j) {
            while(++i<=right && s[i] < pivot);
            while(--j>=left && s[j] > pivot);
            
            if(i<j) {
                int t = s[i]; s[i] = s[j]; s[j] = t;
            }
        }
        
        s[left] = s[j]; s[j] = pivot;
        
        return j;
    }
}

class Select {

    public static void sort(int[] s, int n) {

        for (int i = n - 1; i >= 0; i--) {
            int j = i;

            for (int k = 0; k < i; k++) {
                if(s[k] > s[j]) {
                    j = k;
                }
            }
            
            int t = s[i]; s[i] = s[j]; s[j] = t;
        }
    }
}

class Shell {

    public static void sort(int[] s, int n) {

        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int t = s[i];
                int j = i - gap;

                while (j >= 0 && t < s[j]) {
                    s[j + gap] = s[j];
                    j -= gap;
                }

                s[j + gap] = t;
            }
        }
    }
}

class Insert {

    public static void sort(int[] s, int n) {

        for (int i = 0; i < n; i++) {
            int t = s[i];
            int j = i - 1;

            while (j >= 0 && t < s[j]) {
                s[j + 1] = s[j];
                j--;
            }

            s[j + 1] = t;
        }
    }
}

class Bubble {

    public static void sort(int[] s, int n) {

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (s[j] > s[j + 1]) {
                    int t = s[j];
                    s[j] = s[j + 1];
                    s[j + 1] = t;
                }
            }
        }
    }
}
